// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code05_PreorderSerializeAndDeserialize {
    // 不提交这个类
    // TreeNode类用于表示二叉树的节点
    // 其中val表示节点的值，left和right分别表示左子节点和右子节点
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    // 提交这个类
    public class Codec {
        // 序列化方法，将二叉树转换为字符串
        public String serialize(TreeNode root) {
            // 创建一个StringBuilder对象，用于构建序列化后的字符串
            StringBuilder builder = new StringBuilder();
            // 调用f方法进行实际的序列化操作
            f(root, builder);
            // 将构建好的字符串返回
            return builder.toString();
        }

        // 用于递归构建序列化字符串的辅助方法
        void f(TreeNode root, StringBuilder builder) {
            // 如果当前节点为null，表示遇到了空节点
            if (root == null) {
                // 按照序列化规则，将#（表示空节点）和逗号（用于分隔节点）添加到builder中
                builder.append("#,");
            } else {
                // 如果当前节点不为空，将节点的值转换为字符串并添加到builder中，然后加上逗号
                builder.append(root.val + ",");
                // 递归地对左子树进行序列化操作
                f(root.left, builder);
                // 递归地对右子树进行序列化操作
                f(root.right, builder);
            }
        }

        // 反序列化方法，将字符串转换为二叉树
        public TreeNode deserialize(String data) {
            // 将输入的字符串按照逗号分隔为字符串数组
            String[] vals = data.split(",");
            // 初始化静态变量cnt为0，表示当前正在处理数组vals中的第0个元素
            cnt = 0;
            // 调用g方法进行实际的反序列化操作，并返回构建好的二叉树的根节点
            return g(vals);
        }

        // 当前数组消费到哪了，静态变量用于记录在反序列化过程中已经处理到数组vals的哪个元素了
        public static int cnt;

        // 用于递归构建二叉树的辅助方法
        TreeNode g(String[] vals) {
            // 获取当前要处理的字符串，它是vals数组中索引为cnt的元素
            String cur = vals[cnt++];
            // 如果当前字符串为#，表示遇到了表示空节点的标识
            if (cur.equals("#")) {
                // 返回null，表示构建一个空节点
                return null;
            } else {
                // 如果当前字符串不为#，将其转换为整数
                int value = Integer.parseInt(cur);
                // 创建一个新的TreeNode节点，其值为这个整数
                TreeNode head = new TreeNode(value);
                // 递归地构建左子树，并将结果赋值给head.left
                head.left = g(vals);
                // 递归地构建右子树，并将结果赋值给head.right
                head.right = g(vals);
                // 返回构建好的节点head，它将作为子树的根节点逐步构建出整个二叉树
                return head;
            }
        }
    }
}